package com.hy.stack;

import java.util.ArrayDeque;
import java.util.Arrays;

public class MaxSlidingWindow {

    /**
     * 1
     *
     *
     * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回滑动窗口中的最大值。
     * 进阶：
     * 你能在线性时间复杂度内解决此题吗？
     *
     * 思路
     * 这是使用单调队列的经典题目。
     *
     * 难点是如何求一个区间里的最大值呢？ （这好像是废话），暴力一下不就得了。
     *
     * 暴力方法，遍历一遍的过程中每次从窗口中在找到最大的数值，这样很明显是O(n×k)的算法。
     *
     * 有的同学可能会想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了， 但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。
     *
     * 此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
     *
     * 其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。
     *
     * @param arr
     * @return
     */
    //利用双端队列手动实现单调队列
    /**
     * 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
     * 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
     */
    public static int[] maxSlidingWindow(int [] arr,int k){
        int n = arr.length;
        int [] res = new int[n - k + 1];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            if (!deque.isEmpty() && deque.peek() < i - k +1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出  前后两个元素比较 最新的元素大的话   弹出原队列的元素
            if (!deque.isEmpty() && arr[deque.peekLast()] < arr[i] ){
                deque.pollLast();
            }
            deque.offer(i);
            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            // 大于 K-1
            if (i >= k - 1){
                int num = arr[deque.peek()];
                res[idx++] = num;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int [] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println("res: "+ Arrays.toString(maxSlidingWindow(nums, k)));
    }
}
